/**
 * 集合
*/
#include <stdlib.h>
#include <string.h>

#ifndef SET
#define SET

// 集合元素类型
#ifndef SetElementType
#define SetElementType int
#endif

typedef int SetName; // 集合名称 = 根节点下标
typedef SetElementType *SetType;

SetType createSet(int capacity) {
    SetType set = calloc(capacity, sizeof(SetElementType));
    memset(set, -1, sizeof(SetElementType)*capacity);
    return set;
}

void freeSet(SetType set) {
    free(set);
}

SetName findSet(SetType s, SetElementType x) {
    // 路径压缩
    if (s[x] < 0) {
        return x;
    } else {
        // 先找到根
        // 把根设为x的父节点
        // 再返回根
        return s[x] = findSet(s, s[x]);
    }
}

void unionSet(SetType s, SetName root1, SetName root2) {
    // 按树的规模归并
    if (s[root2] < s[root1]) {
        // root2 节点多, root1挂在root2上，在root2上加上root1的节点
        s[root2] += s[root1]; 
        s[root1] = root2;
    } else {
        // root1 节点多, root2挂在root1上
        s[root1] += s[root2]; 
        s[root2] = root1;
    }
}

// 废弃的版本
// SetName find0(SetType s, SetElementType x) {
//     // 初始集合元素值为-1
//     for (; s[x] >= 0; x=s[x]) ;
//     return x;
// }

// void unionSet0(SetType s, SetName root1, SetName root2) {
//     s[root2] = root1;
// }

// void unionSet2(SetType s, SetName root1, SetName root2) {
//     // 按树的高度归并
//     if (s[root2] < s[root1]) {
//         // root2 比较高, root1挂在root2上
//         s[root1] = root2;
//     } else {
//         // root1 比较高或等高, root2挂在root1上
//         if (s[root1] == s[root2]) {
//             // 等高，高度+1
//             s[root1]--;
//         }
//         s[root2] = root1;
//     }
// }

#endif
